Дискретне перетворення Фур’є (ДПФ) та швидке перетворення Фур’є (ШПФ

Інформація про навчальний заклад

ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра автоматизованих систем управління

Інформація про роботу

Рік:
2009
Тип роботи:
Лабораторна робота
Предмет:
Інформаційні технології
Група:
КН

Частина тексту файла

Міністерство освіти і науки України Національний університет «Львівська політехніка» Інститут комп’ютерних наук та інформаційних технологій Кафедра автоматизованих систем управління Звіт до лабораторної роботи №3 Дискретне перетворення Фур’є (ДПФ) та швидке перетворення Фур’є (ШПФ). ЛАБОРАТОРНА РОБОТА №3 Тема: Дискретне перетворення Фур’є (ДПФ) та швидке перетворення Фур’є (ШПФ). Мета: Навчитися працювати з ДПФ та ШПФ. Теоретичні відомості: Дискретне перетворення Фур(є (ДПФ): ДПФ - це перетворення Фур(є послідовності кінцевої довжини, що є сама по собі також послідовністю, а не перервною функцією і відповідає рівновіддаленим за частотою вибіркам перетворення Фур(є-сигнала. ДПФ – вводиться як : ,  де х(nT) (n=0,…, N-1)- послідовність з N-часових відліків з періодом T; X(k)- послідовність (k=0,…,N-1) з N-частотних відліків; . Формула (3.1) - пряме ДПФ. Формула (3.2) - обернене ДПФ. ДПФ у матричній формі: , (3.3) де X і x – N-вимірні вектори, X=[X(0),X(1),…,X(N-1)]T, х=[x(0),x(T),…,x((N-1)Т)]T; WN-матриця розміром N*N з елементами d(n,k), n,k-індекси за рядком, за стовпчиком d(n,k)=WNnk ; n,k=0,1,2,…N-1. Формула (3.1) - пряме ДПФ у матричній формі. Обернена форма формули: x=WN-1X, (3.4) де WN-1 - обернена матриця до матриці WN, тобто її елемент; d-1(n,k)=1/N*WN-nk . ДПФ вводиться для представлення як періодичних послідовностей з періодом N-відліків, так і послідовності кінцевої довжини N. Коефіцієнти ДПФ кінцевої послідовності дорівнюють значенням її у z-перетворенні у N-точках рівномірно розподілених по одиничному колу. Формула одиничного кола: , де к-0,1,2,…N-1. ДПФ виконується над кінцевою послідовністю N-відліків або над періодичною послідовністю, період якої складається також з N-відліків. Оскільки характеристики спектра послідовностей таких як спектральна густина потужності, амплітуди, фази окремих частот на практиці визначають з використанням тільки кінцевого числа відліків. Звідси випливає, що ДПФ є одним з найважливіших засобів їх визначення. Властивості ДПФ: 1.Властивість лінійності.  (3.5) 2.Зсув ДПФ. Нехай , а y(nT) отримується з x(nT) шляхом зсуву на n0 відліків.  (3.6) , (3.7) де K0-зсув спектра. 3.Властивість симетрії Якщо послідовність x(nT) є дійсною то її ДПФ задовольняє таким умовам симетрії: Дійсна частина: Re(X(k))=Re(X(N-k)) Уявна частина: Im(X(k))= -Im(X(N-k))  (3.8) Наслідки від властивостей ДПФ: 1) ДПФ симетричної послідовності буде дійсною, тобто Якщо x (nT)= x ((N-n)T) ( Im (Х(k))=0 2.) Властивість симетрії дозволяє за допомогою одного ДПФ перетворити одночасно дві дійсних послідовності. Якщо  ДПФ то  Тоді:  (3.9) 4) Згортка по колу. Нехай уU(nT) є згорткою по колу сигналів x (nT) и y(nT) а) , тоді її ДПФ  б) Якщо  то її ДПФ також є згорткою  5.) Спряжена форма обернення. Обернене ДПФ за формулою (3.2) можна обчислити за допомогою формул для прямого ДПФ. , де - комплексне спряження від p  (3.10) Алгоритми швидких перетворень Фур(є (ШПФ): Обчислення ДПФ потребує великої кількості операцій (формула 3.1): приблизно N2 додавань і N2 добутків. Якщо розглянути для реальних частин (розпишемо комплекс через уявну і дійсну частини), то операцій буде в 4 рази більше.  Отримуємо 4N2 операцій множення, додавання трохи менше. Так як кількість обчислень, а значить і час обчислення пропорційне N2, то при прямому методі обчислень ДПФ число арифметичних операцій різко зростає зі збільшенням N, тому були розроблені алгоритми, що зменшують число операцій, які називаються ШПФ. Найчастіше застосовується : ; - натуральне число(оптимальний випадок для БПФ. Основна ідея, що лежить в основі усіх ШПФ, полягає в зведенні N-точкового ШПФ до обчислення декількох N1-точечних ДПФ, при чому N1<<N. Існує два великих ділення. Алгоритми, при реалізації яких потрібна перестановка відліків x(nT) вхідної послідовності, називаються алгоритмами з проріджуванням за часом....
Антиботан аватар за замовчуванням

01.01.1970 03:01

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, увійдіть або зареєструйтесь.

Завантаження файлу

Якщо Ви маєте на своєму комп'ютері файли, пов'язані з навчанням( розрахункові, лабораторні, практичні, контрольні роботи та інше...), і Вам не шкода ними поділитись - то скористайтесь формою для завантаження файлу, попередньо заархівувавши все в архів .rar або .zip розміром до 100мб, і до нього невдовзі отримають доступ студенти всієї України! Ви отримаєте грошову винагороду в кінці місяця, якщо станете одним з трьох переможців!
Стань активним учасником руху antibotan!
Поділись актуальною інформацією,
і отримай привілеї у користуванні архівом! Детальніше

Оголошення від адміністратора

Антиботан аватар за замовчуванням

пропонує роботу

Admin

26.02.2019 12:38

Привіт усім учасникам нашого порталу! Хороші новини - з‘явилась можливість кожному заробити на своїх знаннях та вміннях. Тепер Ви можете продавати свої роботи на сайті заробляючи кошти, рейтинг і довіру користувачів. Потрібно завантажити роботу, вказати ціну і додати один інформативний скріншот з деякими частинами виконаних завдань. Навіть одна якісна і всім необхідна робота може продатися сотні разів. «Головою заробляти» продуктивніше ніж руками! :-)

Новини